package chapter13;

/**
 * 红黑树
 * <p>
 * 目的：
 * 平衡：让任何一条简单路径不比其他简单路径长出2倍
 * <p>
 * 性质：
 * 1.每个节点是红色或者黑色
 * 2.根节点是黑色的
 * 3.每个叶子节点(nil)是黑色的
 * 4.如果一个节点是红色,则它两个子节点是黑色的
 * 5.对于每个节点,从该节点到每个子节点的简单路径上的黑色节点数量是相同的
 * <p>
 * 旋转：
 * 1.rr-右旋
 * 2.lr-左旋
 * *
 * *      Y               X
 * *     / \     rr      / \
 * *    X   c  <---->   a   Y
 * *   / \       lr        / \
 * *  a   b               b   c
 * <p>
 * 指针：
 * 1.Node.root 根节点
 * 2.Node.parent 父节点
 * 3.Node.left 左孩子
 * 4.Node.right 右孩子
 * <p>
 * 调平:
 * 调平会沿着当前操作节点的路径上升,直到"平衡"
 * 因为局部子树的平衡 不代表 其父级子树也平衡,需要沿着当前节点到根节点的简单路径上升,不断调平
 */
public class RBTree {

    /**
     * 模拟null节点,叶子节点都是黑色,根节点也是黑色
     */
    static Node nil = new Node(-1);

    /**
     * 左旋
     */
    public static void leftRotate(Node T, Node x) {
        // 将y.left挂到x.right,再将x挂到y.left
        Node y = x.right;
        x.right = y.left;
        if (y.left != nil) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        // 设置root
        if (x.parent == nil) {
            T.root = y;
        } else if (x.key == x.parent.left.key) { // 看看x是在左边还是右边
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    /**
     * 右旋
     */
    public static void rightRotate(Node T, Node x) {
        // 将x.right挂到y.left,再将y挂到x.right
        Node y = x.left;
        x.left = y.right;
        if (y.right != nil) {
            y.right.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == nil) {
            T.root = y;
        } else if (x.key == x.parent.left.key) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.right = x;
        x.parent = y;
    }

    /**
     * 插入的节点都是红色,不违反性质5
     *
     * @param T
     * @param z
     */
    public static void rbTreeInsert(Node T, Node z) {
        Node y = nil;
        Node x = T.root;
        z.color = 0;// red
        // 找到一个合适的叶子节点
        while (x != nil) {
            // 将找到的节点给y作为z的父节点
            y = x;
            if (z.key < x.key) {
                x = x.left;
            } else {
                x = x.right;
            }
            z.parent = y;
        }
        if (y == nil) {
            T.root = z;
        } else if (z.key < y.key) {
            y.left = z;
        } else {
            y.right = z;
        }
        // 调平
        // 虽然插入一个节点是红色不违反性质5
        // 但是可能会违反性质2/3/4
        rbInsertFixUp(T, z);
    }

    /**
     * 调平情况：
     * case1:如果z的右边叔叔节点是红色,则将z的父节点和叔节点设置为黑色
     * case2:如果z的右边叔叔节点是黑色,并且z是在父节点的右边,则进行左旋
     * case3:如果z的右边叔叔节点是黑色,并且z是在父节点的左边,则进行右旋
     * <p>
     * * case1:
     * *     C(black)
     * *    /       \
     * *   a(red)   d(red)
     * *    \
     * *     b(red)
     * <p>
     * * case2:
     * *    C(black)
     * *   /
     * *  a(red)
     * *   \
     * *    b(red)
     * <p>
     * * case3:
     * *     C(black)
     * *    /
     * *   b(red)
     * *  /
     * * a(red)
     * *
     */
    public static void rbInsertFixUp(Node T, Node z) {
        // z的父节点是红色,违反性质4
        while (z.parent.color == 0) {
            // 如果z的父节点是一个左边节点
            if (z.parent.parent.left.key == z.parent.key) {
                // z的叔叔节点
                Node y = z.parent.parent.right;
                // case1:如果z的右边叔叔节点是红色,则将z的父节点和叔节点设置为黑色
                if (y.color == 0) {
                    z.parent.color = 1;
                    z.parent.parent.color = 0;
                    y.color = 1;
                    z = z.parent.parent;
                } else if (z.key == z.parent.right.key) { // case2:如果z的右边叔叔节点是黑色,并且z是在父节点的右边,则进行左旋
                    z = z.parent;
                    leftRotate(T, z);
                }
                // case3:如果z的右边叔叔节点是黑色,并且z是在父节点的左边,则进行右旋
                z.parent.color = 1;
                z.parent.parent.color = 0;
                rightRotate(T, z.parent.parent);
            } else {
                // 同上,对称
                Node y = z.parent.parent.left;
                if (y.color == 0) {
                    z.parent.color = 1;
                    z.parent.parent.color = 0;
                    y.color = 1;
                    z = z.parent.parent;
                } else if (z.key == z.parent.left.key) {
                    z = z.parent;
                    rightRotate(T, z);
                }
                z.parent.color = 1;
                z.parent.parent.color = 0;
                leftRotate(T, z.parent.parent);
            }
        }
        // 根节点一定是黑色
        T.root.color = 1;
    }

    /**
     * 在树T上把以u为父节点的子树替换成以v为父节点的子树
     */
    public static void rbTransplant(Node T, Node u, Node v) {
        // u的父节点为nil则v是root
        if (u.parent == nil) {
            T.root = v;
        } else if (u.key == u.parent.left.key) { // 如果u在左边则替换左边,在右边替换右边
            u.parent.left = v;
        } else {
            u.parent.right = v;
        }
        // 替换父节点
        v.parent = u.parent;
    }

    public static Node min(Node x) {
        while (x.left != null && x.left != nil) {
            x = x.left;
        }
        return x;
    }

    /**
     * *    z
     * *     \
     * *      b
     * *
     * *    z
     * *   /
     * *  a
     * *
     * *    z
     * *   / \
     * *  a   b
     */
    public static void rbTreeDelete(Node T, Node z) {
        Node x;
        Node y = z;
        int yOriginalColor = y.color;
        // 如果待删除节点的左孩子是nil,则把右孩子挂到父节点
        if (z.left == nil) {
            x = z.right;
            rbTransplant(T, z, z.right);
        } else if (z.right == nil) { // 如果待删除节点的右孩子是nil,则把左孩子挂到父节点
            x = z.left;
            rbTransplant(T, z, z.left);
        } else { // 如果左右孩子都在
            // 后继
            y = min(z.right);
            // 记录操作的节点y颜色,涉及到移动,可能会违反红黑树性质
            yOriginalColor = y.color;
            x = y.right;
            //
            if (y.parent.key == z.key) {
                x.parent = y;
            } else {
                // 构建一个新的y,将原先z的右边挂到y上,因为y的z的后继,是比z.left子树大,并且小于其他z.right子树的节点
                // y.parent.left = nil
                rbTransplant(T, y, y.right);
                // 把z.right挂到y的右边
                y.right = z.right;
                y.right.parent = y;
            }
            // 然后将y移动到原先z的位置
            rbTransplant(T, z, y);
            // 讲z.left挂到y.left
            y.left = z.left;
            y.left.parent = y;
            // 将原先z的颜色给到y
            y.color = z.color;
        }
        // 如果是移动的黑色节点,需要重新调平
        if (yOriginalColor == 1) {
            rbDeleteFixUp(T, x);
        }
    }

    /**
     * case1:如果兄弟节点是红色,将兄弟节点设置为黑色,父节点设置为红色,然后左旋
     * case2:如果兄弟节点是黑色,兄弟的左右子节点都是黑色,将兄弟节点设置为红色
     * case3:如果兄弟节点是黑色,如果兄弟左孩子是红色,则置黑,自己置红,右旋
     * case4:如果兄弟节点是黑色,如果兄弟右孩子是红色,则置黑,自己置红,左旋
     * <p>
     * * case1:
     * *           B(black)
     * *         /         \
     * *     (x)A(black) (w)D(red)
     * *                 /     \
     * *             C(black)  E(black)
     * *
     * * case2:
     * *           B(red)
     * *         /         \
     * *     (x)A(black) (w)D(red)
     * *                 /     \
     * *             C(black)  E(black)
     * *
     * * case3:
     * *           B(red)
     * *         /         \
     * *     (x)A(black) (w)D(red)
     * *                 /     \
     * *             C(red)  E(black)
     * *
     * * case4
     * *           B(red)
     * *         /         \
     * *     (x)A(black) (w)D(red)
     * *                 /     \
     * *             C(black)  E(red)
     * *
     */
    public static void rbDeleteFixUp(Node T, Node x) {
        // 如果x不是根节点却是黑色
        while (x.key != T.root.key && x.color == 1) {
            Node w;
            // 如果x在左边
            if (x.key == x.parent.left.key) {
                // w兄弟节点
                w = x.parent.right;
                // case1:如果兄弟节点是红色,将兄弟节点设置为黑色,父节点设置为红色,然后左旋
                if (w.color == 0) {
                    w.color = 1;
                    x.parent.color = 0;
                    leftRotate(T, x.parent);
                    w = x.parent.right;
                }
                // case2:如果兄弟节点是黑色,兄弟的左右子节点都是黑色,将兄弟节点设置为红色
                if (w.left.color == 1 && w.right.color == 1) {
                    w.color = 0;
                    x = x.parent;
                } else if (w.right.color == 1) { // case3:如果兄弟节点是黑色,如果兄弟左孩子是红色,则置黑,自己置红,右旋
                    w.left.color = 1;
                    w.color = 0;
                    rightRotate(T, w);
                    w = x.parent.right;
                }
                // case4:如果兄弟节点是黑色,如果兄弟右孩子是红色,则置黑,自己置红,左旋
                w.color = x.parent.color;
                x.parent.color = 1;
                w.right.color = 1;
                leftRotate(T, x.parent);
                x = T.root;
            } else {
                // 同上,对称
                w = x.parent.left;
                if (w.color == 0) {
                    w.color = 1;
                    x.parent.color = 0;
                    rightRotate(T, x.parent);
                    w = x.parent.left;
                }
                if (w.left.color == 1 && w.right.color == 1) {
                    w.color = 0;
                    x = x.parent;
                } else if (w.left.color == 1) {
                    w.right.color = 1;
                    w.color = 0;
                    leftRotate(T, w);
                    w = x.parent.left;
                }
                w.color = x.parent.color;
                x.parent.color = 1;
                w.left.color = 1;
                rightRotate(T, x.parent);
                x = T.root;
            }
        }
        x.color = 1;
    }

    public static Node iterativeTreeSearch(Node x, int k) {
        while (x != null && x.key != k) {
            if (k < x.key) {
                x = x.left;
            } else {
                x = x.right;
            }
        }
        return x;
    }

    static class Node {
        public Node left;
        public int key;
        public Node right;
        public Node parent;
        public Node root;
        /**
         * 0 red 1 black
         */
        public int color;

        public Node() {
        }

        public Node(int key) {
            this.key = key;
        }
    }
}
